package team3;

import java.util.*;

/**Implementation of a MinMax Tree for Reversi.
 * <p>
 * A min max tree is a tree structure such that each node represents a specific
 * state of the (in this case: board), and the children of each node can be
 * reached through a single action (a move). The Min Max tree uses the concept
 * that any opponent will always try to maxamize the 'goodness' of a board, where
 * goodness is correlated to the likelyhood of winning. So, the job of an opponent
 * is to minimize your goodness, while maxamizing his own. The Min Max tree
 * goes about this by, at every level, alternating between minimizing and
 * maxamizing the values from each node.
 * <p>
 * In the end, you will get a list of moves, and their associated goodness,
 * which is the best possible outcome of the move, given that each player is
 * playing perfectly, to the best of their abilities.
 * <p>
 * This was initially implemented with a Tree Data Structure, but after troubles
 * encountered with the memory requirements, was changed to an 'implicit'
 * structure formed through recursive calls to a 'calculateGoodness' function:
 * This has the advantage that there are never more then a few Board States floating
 * in memmory, but has the disadvantage that, if you are evaluating the tree to
 * a depth of 5, each evaluation requires regenerating all board states that
 * can be reached in five moves. As a result, this is costly in terms of CPU time.
 */
public class MinMaxTree
{
    AI.Player player;
	BoardState initialState;

    /**Builds a min/max tree
     * @param state State the min/max tree will be branching off of
     * @param player Player to try and optimize for- the person we are returning suggestions to.
     */
    public MinMaxTree(BoardState state, AI.Player player) 
	{
		initialState=state;
        this.player=player;
    }

    /**Determines the best scoring move that can be made from the starting board state.
     * @param depth Depth to search to for evaluating move goodness.
     * @param goodness Goodness function to use when evaluating boards.
     * @return Best move for the depth and goodness function, or BoardState.INVALID_MOVE if moves available.
     */
    public int[] getBestMove(int depth, GoodnessFunction goodness) {
        Map<int[], Double> evaluation = evaluateTree(depth, goodness);

        int[] bestMove = BoardState.INVALID_MOVE;
        double bestGoodness = Double.NEGATIVE_INFINITY;
        for (int[] key : evaluation.keySet())
        {
            double currentGoodness = evaluation.get(key);
            if(currentGoodness > bestGoodness)
            {
                bestMove = key;
                bestGoodness = currentGoodness;
            }
        }
        return bestMove;
    }

    /** Determines the score for all possible moves that can be made
     * from the current board state, given a goodness function.
     * @param depth Depth to search to
     * @param goodness Goodness function for evaluating moves
     * @return A map from a valid move to its estimated goodness. Map will be size 0 if no valid moves are possible.
     */
    public Map<int[], Double> evaluateTree(int depth, GoodnessFunction goodness)
	{
        Map<int[], Double> map = new HashMap<int[], Double>();
		boolean playerIsBlack = player==AI.Player.BLACK;
		AI.Player nextPlayer = playerIsBlack ? AI.Player.WHITE : AI.Player.BLACK;
	    for(int[] move : initialState.getAvailableMoves(player))
		{
			BoardState nextState = initialState.makeMove(player, move);
			double value = calculateGoodness(nextState, nextPlayer, depth, goodness);
            map.put(move, value);
        }
        return map;
    }

    /**Determines the goodness of a board state by either calculating the goodness
     * of the state, or by taking the min or max goodness value of all possible moves
     * from that state, dependent on the player making the move.
     * @param state Board State that the next player would be making a move from.
     * @param nextMoveForPlayer The player who would be making a move off <code>state</code>
     * @param depth Depth to search for determining goodness.
     * @param goodness Method for calculating Board Goodness.
     * @return The estimated goodness of the board state.
     */
	private double calculateGoodness(BoardState state, AI.Player nextMoveForPlayer, int depth, GoodnessFunction goodness)
	{
        //reached the end of the tree, evaluate goodness
        if(depth==0)
            return goodness.evaluateGoodness(state, player);

        //only maxamize if the player making the move is the player running min/max
		boolean shouldMaxamize = nextMoveForPlayer == player;
		boolean playerIsBlack = nextMoveForPlayer == AI.Player.BLACK;
		AI.Player nextPlayer = playerIsBlack ? AI.Player.WHITE : AI.Player.BLACK;
		double bestValue = shouldMaxamize ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;

        Collection<int[]> moves = state.getAvailableMoves(nextMoveForPlayer);
        //no moves means either end game, or player has to pass; try calculating next stage
		if(moves.size()==0)
			return calculateGoodness(state, nextPlayer, depth-1, goodness);
		for(int[] move : moves)
		{
			BoardState nextState = state.makeMove(nextMoveForPlayer, move);
			double currentValue = calculateGoodness(nextState, nextPlayer, depth-1, goodness);
            //if value larger and maxamizing, or value smaller and minimizing
            if((currentValue > bestValue && shouldMaxamize) ||(currentValue < bestValue && !shouldMaxamize))
                bestValue = currentValue;
		}
		return bestValue;
	}
}
